#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
        vector<int> ones;
        vector<int> zeros;
    public:
        int find_max_form(vector<string> &strs, int n, int z, int o)
        {
                if(n == strs.size()){
                        return 0;
                }

                int val = find_max_form(strs, n + 1, z, o);
                if(ones[n] <= o && zeros[n] <= z){
                        val = max(val, find_max_form(strs, n + 1, z - zeros[n], o - ones[n]) + 1);
                }
                return val;
        }

        int find_max_form(vector<string> &strs, int n, int z, int o, vector<vector<vector<int>>> &recd)
        {
                if(n == strs.size()){
                        return 0;
                }

                if(recd[n][z][o] != -1){
                        return recd[n][z][o];
                }

                int val = find_max_form(strs, n + 1, z, o, recd);
                if(ones[n] <= o && zeros[n] <= z){
                        val = max(val, find_max_form(strs, n + 1, z - zeros[n], o - ones[n], recd) + 1);
                }
                return recd[n][z][o] = val;
        }

        int find_max_dp(vector<string> &strs, int n, int z, int o)
        {
                vector<vector<vector<int>>> dp(strs.size() + 1, vector<vector<int>>(z + 1, vector<int>(o + 1, 0)));
                for(int i = strs.size() - 1; i >= 0; i--){
                        for(int j = 0; j <= z; j++){
                                for(int k = 0; k <= o; k++){
                                        dp[i][j][k] = dp[i + 1][j][k];
                                        if(ones[i] <= k && zeros[i] <= j){
                                                dp[i][j][k] = max(dp[i][j][k], dp[i + 1][j - zeros[i]][k - ones[i]] + 1);
                                        }
                                }
                        }
                }
                return dp[0][z][o];
        }

        int find_max_dp(vector<string> &strs, int z, int o)
        {
                vector<vector<int>> dp(z + 1, vector<int>(o + 1, 0));
                for(int i = strs.size() - 1; i >= 0; i--){
                        for(int j = z; j >= zeros[i]; j--){
                                for(int k = o; k >= ones[i]; k--){
                                        dp[j][k] = max(dp[j][k], dp[j - zeros[i]][k - ones[i]] + 1);
                                }
                        }
                }
                return dp[z][o];
        }

	int findMaxForm(vector<string> &strs, int m, int n)
	{
                for(auto &s : strs){
                        int cnt = count(s.begin(), s.end(), '1');
                        ones.push_back(cnt);
                        cnt = count(s.begin(), s.end(), '0');
                        zeros.push_back(cnt);
                }

                vector<vector<vector<int>>> recd(strs.size(), vector<vector<int>>(m + 1, vector<int>(n + 1, -1)));

                return find_max_dp(strs, m, n);
	}
};

int main()
{
        vector<string> strs = {"10", "0001", "111001", "1", "0"};
        int m = 5, n = 3;
        cout<<Solution().findMaxForm(strs, m, n)<<endl;
        return 0;
}
